#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <condition_variable>
#include <mutex>
#include <queue>
#include <optional>

using Matrix = std::vector<std::vector<int>>;

static bool bankers_safe_sequence(const std::vector<int>& available,
                                  const Matrix& max_need,
                                  const Matrix& allocation,
                                  std::vector<int>& seq_out) {
    size_t n = allocation.size();
    size_t m = available.size();
    std::vector<int> work = available;
    std::vector<bool> finish(n, false);
    Matrix need(n, std::vector<int>(m));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
            need[i][j] = max_need[i][j] - allocation[i][j];

    seq_out.clear();
    bool progress = true;
    while (progress) {
        progress = false;
        for (size_t i = 0; i < n; ++i) {
            if (!finish[i]) {
                bool can_finish = true;
                for (size_t j = 0; j < m; ++j) if (need[i][j] > work[j]) { can_finish = false; break; }
                if (can_finish) {
                    for (size_t j = 0; j < m; ++j) work[j] += allocation[i][j];
                    finish[i] = true;
                    seq_out.push_back(static_cast<int>(i));
                    progress = true;
                }
            }
        }
    }
    for (bool f : finish) if (!f) return false;
    return true;
}

static bool bankers_can_grant_request(int proc,
                                      const std::vector<int>& request,
                                      const std::vector<int>& available,
                                      const Matrix& max_need,
                                      const Matrix& allocation) {
    size_t m = available.size();
    size_t n = allocation.size();
    Matrix need(n, std::vector<int>(m));
    for (size_t i = 0; i < n; ++i)
        for (size_t j = 0; j < m; ++j)
            need[i][j] = max_need[i][j] - allocation[i][j];

    // Request <= Need && Request <= Available
    for (size_t j = 0; j < m; ++j) {
        if (request[j] > need[proc][j]) return false;
        if (request[j] > available[j]) return false;
    }

    // simulate grant
    std::vector<int> new_available = available;
    Matrix new_allocation = allocation;
    for (size_t j = 0; j < m; ++j) {
        new_available[j] -= request[j];
        new_allocation[proc][j] += request[j];
    }

    std::vector<int> seq;
    return bankers_safe_sequence(new_available, max_need, new_allocation, seq);
}

int main() {
    // 银行家算法
    std::vector<int> available = {3, 3, 2, 1};
    Matrix max_need = {
        {2, 0, 0, 1}, // P0
        {3, 1, 2, 1}, // P1
        {2, 1, 0, 3}, // P2
        {1, 3, 1, 2}, // P3
        {1, 4, 3, 2}, // P4
    };
    Matrix allocation = {
        {4, 2, 1, 2}, // P0
        {5, 2, 5, 2}, // P1
        {2, 3, 1, 6}, // P2
        {1, 4, 2, 4}, // P3
        {3, 6, 6, 5}, // P4
    };

    std::vector<int> seq;
    bool safe = bankers_safe_sequence(available, max_need, allocation, seq);
    std::cout << "Safe: " << (safe ? "true" : "false") << ", Sequence: ";
    for (size_t i = 0; i < seq.size(); ++i) std::cout << "P" << seq[i] << (i+1<seq.size()?" ":"");
    std::cout << std::endl;

    std::vector<int> p1_req = {1,1,0,0};
    std::vector<int> p4_req = {0,0,2,0};
    std::cout << "P1 request grantable: "
              << (bankers_can_grant_request(1, p1_req, available, max_need, allocation) ? "true" : "false")
              << std::endl;
    std::cout << "P4 request grantable: "
              << (bankers_can_grant_request(4, p4_req, available, max_need, allocation) ? "true" : "false")
              << std::endl;

    return 0;
}